﻿using System.Diagnostics.CodeAnalysis;

namespace LJ.Host.Abstractions.Extensions;

/// <summary>
/// 排序
/// </summary>
public static class SortExtensions
{
    public static List<TopologicalItem<T>> TopologicalSort<T>(this IEnumerable<TopologicalItem<T>> source)
        where T:notnull
    {
        var sorted = new List<TopologicalItem<T>>();
        var visited = new Dictionary<TopologicalItem<T>, bool>();

        foreach (var item in source)
        {
            Visit(item,  sorted, visited);
        }

        return sorted;
    }

    private static void Visit<T>(TopologicalItem<T> item,  List<TopologicalItem<T>> sorted, Dictionary<TopologicalItem<T>, bool> visited)
        where T : notnull
    {
        var alreadyVisited = visited.TryGetValue(item, out bool inProcess);

        // 如果已经访问该顶点，则直接返回
        if (alreadyVisited)
        {
            // 如果处理的为当前节点，则说明存在循环引用
            if (inProcess)
            {
                throw new ArgumentException("Cyclic dependency found.");
            }
        }
        else
        {
            // 正在处理当前顶点
            visited[item] = true;

            // 获得所有依赖项
            var dependencies = item.Dependencies;
            // 如果依赖项集合不为空，遍历访问其依赖节点
            if (dependencies != null)
            {
                foreach (var dependency in dependencies)
                {
                    // 递归遍历访问
                    Visit(dependency, sorted, visited);
                }
            }

            // 处理完成置为 false
            visited[item] = false;
            sorted.Add(item);
        }
    }
}

public class TopologicalItem<T>(T value) : IEqualityComparer<TopologicalItem<T>>
    where T : notnull
{
    public T Value { get; private set; } = value;
    // 依赖项
    public List<TopologicalItem<T>> Dependencies { get; private set; } = [];

    public bool Equals(TopologicalItem<T>? x, TopologicalItem<T>? y)
    {
        if (x==null && y==null)
        {
            return true;
        }
        if (x?.GetHashCode()==y?.GetHashCode())
        {
            return true;
        }
        return false;
    }

    public int GetHashCode([DisallowNull] TopologicalItem<T> obj)
    {
        return obj.Value.GetHashCode();
    }
}

